package com.xk._02算法篇._02unionFind.union;

/**
 * @description: Quick Find
 * @author: xu
 * @date: 2022/10/4 20:27
 */
public class UnionFind_QF extends UnionFind{

    public UnionFind_QF(int capacity) {
        super(capacity);
    }

    //O(1)
    // 父节点都是根节点
    @Override
    public int find(int v){
        rangeCheck(v);
        return parents[v];
    }

    //O(n)
    // 将 v1 所在集合的所有元素都嫁接到 v2 的父节点上
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;

        for (int i = 0; i < parents.length; i++) {
            if (parents[i] == p1) {
                parents[i] = p2;
            }
        }
    }

}
